package com.cqs.leetcode.dp;

import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.Set;

public class JumpGame55 {


    public boolean canJump(int[] nums) {
        if (nums == null || nums.length == 0) return false;
        int[] dp = new int[nums.length];
        Arrays.fill(dp, -1);
        return jump(nums, nums.length - 1, dp);
    }

    private boolean jump(int[] nums, final int pos, int[] dp) {
        if (pos == 0) {
            dp[pos] = 1;
        }
        if (dp[pos] == -1) {
            for (int r = pos - 1; r >= 0; --r) {
                if (pos - r <= nums[r] && jump(nums, r, dp)) {
                    dp[pos] = 1;
                }
            }
            if (dp[pos] != 1) dp[pos] = 0;
        }
        return dp[pos] == 1;
    }

    public static void main(String[] args) {
        JumpGame55 jump = new JumpGame55();
        Set<int[]> testCases = new LinkedHashSet<>();
        testCases.add(new int[]{2, 3, 1, 1, 4});
        testCases.add(new int[]{3,2,1,0,4});
        testCases.add(new int[]{2,0});
        testCases.forEach(it -> System.out.println(jump.canJump(it)));
    }
}
